package leetcode_ago;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 打印杨辉三角
 * 给定一个非负整数numRows，生成杨辉三角的前numRows行。
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 */
public class Num118_YangHui {
    /**
     * 分析：杨辉三角特点
     * 1）每一行元素个数和行数相同
     * 2）每一行第一个元素和最后一个元素都是1，固定值
     * 3）第i行第j列等于第i-1行j-1列+i-1行第j列【[i,j]=[i-1,j-1]+[i-1,j]】每一行第一个和最后一个元素都是1，此处j至少从第二列开始计算
     * 注意：i和j表示实际行数和列数，默认都从1计数，但是索引都是从0开始计数的，因此和实际的行和列遍历时注意索引
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret=new ArrayList<>();
        //先写出特殊的前两行，元素都是1
        /**Arrays.asList是一个可变参数列表
         * （）中放可变参数，里面有几个元素就放几个元素
         * 就不用new ArrayList了
         */
        List<Integer> first= Arrays.asList(1);//元素[1]加入第一行
        ret.add(first);
        if(numRows==1){
            return ret;
        }
        List<Integer> second=Arrays.asList(1,1);//元素1，1组成的数组[1,1]加入第二行
        ret.add(second);
        if(numRows==2){
            return ret;
        }
        //次数numRows至少三行。开始遍历行列数
        //i行j列元素[i,j]=[i-1,j]+[i-1,j-1]
        for (int i = 3; i <= numRows; i++) {
            //记录i-1行元素集合
            List<Integer> prev=ret.get(i-1-1);//i-1行下标索引为i-1-1
            //记录当前行（i行）元素,数组集合存储
            List<Integer> cur=new ArrayList<>();
            cur.add(1);
            //j从第二列开始，到倒数第二列。因为第一列和最后一列元素为1
            for (int j = 2; j <i ; j++) {
                int val= prev.get(j-1-1)+prev.get(j-1);
                cur.add(val);
            }
            cur.add(1);
            ret.add(cur);
        }
        return ret;
    }

}
